package org.hot100_0.leetcode5;

import org.leetcode.easy.ListNode;

import java.util.ArrayList;
import java.util.List;

public class Solution {

    /**
     *  方法1：用动态规划的思想：当前回文子串依赖于前一步的结果
     *  方法2：暴力获取所有的连续回文子集，找到最长的。
     */
    public static void main(String[] args) {
        String str = continuousSubsets2("cbbd");
        System.out.println(str);
    }

    //动态规划
    public static String longestPalindrome(String s) {

        int n = s.length();

        if (n == 1) {
            return s;
        }

        boolean[][] dp = new boolean[n][n];

        dp[0][0] = true;

        int maxLength = 0;

        String res = String.valueOf(s.charAt(0));

        for (int right = 0; right < n; right++) {
            for (int left = 0; left < right; left++) {
                if (s.charAt(left) == s.charAt(right)) {
                    if (dp[left + 1][right - 1] || right - left <= 2) {
                        dp[left][right] = true;

                        if (right - left + 1 > maxLength) {
                            maxLength = right - left + 1;
                            res = s.substring(left, right + 1);
                        }
                    }
                }
            }
        }

        return res;
    }

    //暴力获取所有回文子集
    public static String continuousSubsets2(String s){
        int n = s.length();

        int maxLength = 0;

        String resStr="";

        for (int right = 0; right < n; right++) {
            for (int left = 0; left <= right; left++) {
                if (right-left>maxLength){
                    if (isPalindrome2(s,left,right)){
                        maxLength=right-left+1;
                        resStr = s.substring(left,right+1);
                    }
                }
            }
        }

        return resStr;
    }

    //超时 --> 暴力获取所有连续子集，再对连续子集中找最长回文子集
    public static List<String> continuousSubsets(String s){
        int n = s.length();

        int maxLength = 0;

        List<String> res=  new ArrayList<>();

        for (int right = 0; right < n; right++) {
            for (int left = 0; left <= right; left++) {
                res.add(s.substring(left,right+1));
            }
        }

        return res;
    }

    public static boolean isPalindrome2(String s,int start,int end) {
        if (start == end) {
            return true;
        }

        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }

            start++;
            end--;
        }

        return true;
    }

    public static boolean isPalindrome(String s) {
        int start = 0;
        int end = s.length()-1;
        if (start == end) {
            return true;
        }

        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }

            start++;
            end--;
        }

        return true;
    }
}
